package com.lw.leetcode.back.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 面试题 17.22. 单词转换
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/18 11:28
 */
public class FindLadders {

    public static void main(String[] args) {
        FindLadders test = new FindLadders();

        // [hit, hot, dot, dog, cog]
//        String beginWord = "hit";
//        String endWord = "cog";
//        List<String> list = Arrays.asList("hot","dot","dog","lot","log","cog");

        // []
//        String beginWord = "hit";
//        String endWord = "cog";
//        List<String> list = Arrays.asList("hot", "dot", "dog", "lot", "log");

        // [hot, hog, dog]
        String beginWord = "hot";
        String endWord = "dog";
        List<String> list = Arrays.asList("hot", "cog", "dog", "tot", "hog", "hop", "pot", "dot");

        List<String> ladders = test.findLadders(beginWord, endWord, list);
        System.out.println(ladders);
    }


    private Set<String> set = new HashSet<>();
    private List<String> values = new ArrayList<>();
    private Map<String, String> pathMap = new HashMap<>();

    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        if (beginWord.equals(endWord)) {
            return values;
        }
        set.addAll(wordList);
        if (!set.contains(endWord)) {
            return values;
        }
        LinkedList<String> l1 = new LinkedList<>();
        LinkedList<String> l2 = new LinkedList<>();
        Map<String, Integer> m1 = new HashMap<>();
        Map<String, Integer> m2 = new HashMap<>();
        l1.add(beginWord);
        l2.add(endWord);
        m1.put(beginWord, 0);
        m2.put(endWord, 0);
        while (!l1.isEmpty() && !l2.isEmpty()) {
            boolean f;
            if (l1.size() <= l2.size()) {
                f = find(l1, m1, m2);
            } else {
                f = find(l2, m2, m1);
            }
            if (f) {
                if (!values.get(0).equals(beginWord)) {
                    Collections.reverse(values);
                }
                return values;
            }
        }
        return values;
    }

    private boolean find(LinkedList<String> list, Map<String, Integer> ma, Map<String, Integer> mb) {
        String poll = list.poll();
        char[] chars = poll.toCharArray();
        int length = chars.length;
        for (int i = 0; i < length; i++) {
            char c = chars[i];
            for (int j = 0; j < 26; j++) {
                chars[i] = (char) (j + 'a');
                String item = String.valueOf(chars);
                if (!set.contains(item)) {
                    continue;
                }
                if (ma.containsKey(item)) {
                    continue;
                }
                if (mb.containsKey(item)) {
                    String s = pathMap.get(poll);
                    while (s != null) {
                        values.add(s);
                        s = pathMap.get(s);
                    }
                    Collections.reverse(values);
                    values.add(poll);
                    values.add(item);

                    s = pathMap.get(item);
                    while (s != null) {
                        values.add(s);
                        s = pathMap.get(s);
                    }
                    return true;
                }
                pathMap.put(item, poll);
                ma.put(item, ma.get(poll) + 1);
                list.add(item);
            }
            chars[i] = c;
        }
        return false;
    }

}
